# 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
#  请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
#
#  示例 1:
# 输入: [3,2,1,5,6,4] 和 k = 2
# 输出: 5
#
#  示例 2:
# 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
# 输出: 4
import heapq
import random
from typing import List


class Solution:
    def findKthLargest3(self, nums: List[int], k: int) -> int:
        """
        容量为k的小根堆
        遍历整个数组
            当 minHeap的容量小于k时直接入堆
            当 minHeap的容量到底了k时
                如果 当前 num 大于 堆顶元素则 将堆顶出堆，然后将当前num入堆(或者将堆顶用num替换，然后将minHeap进行堆化堆化)
        最后返回堆顶元素即可
        :param nums:
        :param k:
        :return:
        """
        minHeap = []
        for num in nums:
            if len(minHeap) < k:
                heapq.heappush(minHeap, num)
            else:
                if num > minHeap[0]:
                    # 方式一:堆顶出堆，然后将当前num入堆
                    # heapq.heappop(minHeap)
                    # heapq.heappush(minHeap, num)
                    # 方式二:将堆顶用num替换，然后将minHeap进行堆化堆化
                    minHeap[0] = num
                    heapq.heapify(minHeap)
        return minHeap[0]

    def findKthLargest2(self, nums: List[int], k: int) -> int:
        """
        基于快排的选择算法
        由于快排每次都能确定一个元素的位置
        所以只要某次划分的 q 为倒数第 k 个下标的时候，我们就已经找到了答案
        至于 a[l⋯q−1] 和 a[q+1⋯r] 是否是有序的，不需要关心
        :param nums:
        :param k:
        :return:
        """
        targetIndex = len(nums) - k

        def quickSelect(start, end) -> int:
            def getPivotIndex(left, right) -> int:  # 确定某个元素的最终位置(轴点元素)，并将小于轴点元素的所有元素放到轴点元素的左边，将大于轴点元素的放到轴点元素的右边
                randomIndex = random.randint(left, right)
                nums[right], nums[randomIndex] = nums[randomIndex], nums[right]  # 在left到right之间取一个随机值，和nums[right]交换
                pivot = nums[right]  # 暂存这个轴点元素的值
                i, j = left, left
                while j < right:
                    if nums[j] <= pivot:
                        nums[i], nums[j] = nums[j], nums[i]
                        i += 1
                    j += 1
                nums[i], nums[right] = nums[right], nums[i]
                return i

            pivotIndex = getPivotIndex(start, end)
            if targetIndex == pivotIndex:
                return nums[pivotIndex]
            else:
                if pivotIndex > targetIndex:
                    return quickSelect(start, pivotIndex - 1)
                else:
                    return quickSelect(pivotIndex + 1, end)

        return quickSelect(0, len(nums) - 1)

    def findKthLargest1(self, nums: List[int], k: int) -> int:
        """
        直接调用系统堆API
        :param nums:
        :param k:
        :return:
        """
        return heapq.nlargest(k, nums)[-1]

    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.findKthLargest3(nums, k)


if __name__ == "__main__":
    nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]
    k = 4
    nums = [3, 2, 1, 5, 6, 4]
    k = 2
    print(Solution().findKthLargest(nums, k))
